Church-Turing Thesis

释义 Definition

丘奇—图灵论题：计算理论中的一个核心观点，认为“任何可由有效方法/算法计算的过程”，都能被某种形式化模型所刻画（典型代表是图灵机、λ演算、或递归函数）。它通常被称为“论题”而非“定理”，因为它连接的是“直觉上的可计算”与“形式化的可计算”，难以用纯数学方式严格证明。

发音 Pronunciation (IPA)

/ˈtʃɝːtʃ ˈtjʊərɪŋ ˈθiːsɪs/

例句 Examples

A Turing machine is one model used to express the Church-Turing thesis.
图灵机是用来表达丘奇—图灵论题的一种模型。

Although different models of computation look very different, the Church-Turing thesis suggests they capture the same notion of what is effectively computable.
尽管不同的计算模型看起来差异很大，丘奇—图灵论题认为它们刻画的是同一种“可有效计算”的概念。

词源 Etymology

该术语以两位奠基者命名：Alonzo Church（阿隆佐·丘奇）与Alan Turing（艾伦·图灵）。20世纪30年代，丘奇提出以λ演算刻画可计算性，图灵提出以图灵机刻画可计算性；两种路径最终在能力上被认为等价，促成了“任何直觉上可有效计算的函数都可由这些形式系统计算”的论题。“Thesis”一词源自希腊语，意为“命题/论题”。

相关词 Related Words

• Computability
• Algorithm
• Turing Machine
• Lambda Calculus
• Recursive Function
• Decidability
• Halting Problem
• Effective Procedure

文学与经典著作中的出现 Literary Works

• Alan Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem” (1936)
• Alonzo Church, “An Unsolvable Problem of Elementary Number Theory” (1936)
• Michael Sipser, **Introduction to the Theory of Computation**（常见教材章节讨论该论题）
• Hartley Rogers Jr., Theory of Recursive Functions and Effective Computability
• Douglas Hofstadter, **Gödel, Escher, Bach**（以通俗方式涉及可计算性与相关思想）